#pragma once
#include<iostream>
#include<vector>
#include<time.h>
using std::cout;
using std::endl;

template<class T>
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;
		//自由链表有数据的话,先重复利用
		if (_freelist)
		{
			obj = (T*)_freelist;
			_freelist = *(void**)_freelist;
		}
		else
		{
			//内存池剩下的地址不足T的大小,把剩下的一点丢掉(或者是第一次开辟,本来就没有空间),重新开辟一块
			if (_remainByte < sizeof(T))
			{
				_remainByte = 128 * 1024;
				_memory = (char * )malloc(_remainByte);
				if (_memory == nullptr)
				{
					throw std::bad_alloc();//开辟失败抛异常
				}
			}
			obj = (T*)_memory;
			//给T划分的大小一定是>=指针大小的,因为将来回收还需要那块空间来记录后续链表的地址
			int objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			_memory += objSize;//_memory为什么要设计成char*的原因
			_remainByte -= objSize;

			//使用定位new来初始化那一段空间
			new(obj)T;//
		}
		return obj;
	}

	void Delete(T* obj)
	{
		obj->~T();//万一T类型有vector之类的容器,要调用它的析构,防止内存泄漏

		//头插
		*(void**)obj = _freelist;//这里二级指针是为了将地址写入obj中
		_freelist = (void*)obj;
	}
private:
	char* _memory = nullptr;//开辟出来的一大块内存的地址,后面被用于对象地址的切分
	int _remainByte = 0;	//开辟出来的内存还剩下多少字节
	void* _freelist = nullptr; //自由链表的头节点
};


struct TreeNode
{
	int _val;
	TreeNode* _left;
	TreeNode* _right;
	TreeNode()
		:_val(0)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

//比较malloc和ObjectPool的性能
void TestObjectPool()
{
	// 申请释放的轮次
	const size_t Rounds = 3;
	// 每轮申请释放多少次
	const size_t N = 100000;
	std::vector<TreeNode*> v1;
	v1.reserve(N);

	size_t begin1 = clock();
	for (size_t j = 0; j < Rounds; ++j)
	{
		for (int i = 0; i < N; ++i)
		{
			v1.push_back(new TreeNode);
		}
		for (int i = 0; i < N; ++i)
		{
			delete v1[i];
		}
		v1.clear();
	}
	size_t end1 = clock();

	ObjectPool<TreeNode> TNPool;
	std::vector<TreeNode*> v2;
	v2.reserve(N);
	size_t begin2 = clock();
	for (size_t j = 0; j < Rounds; ++j)
	{
		for (int i = 0; i < N; ++i)
		{
			v2.push_back(TNPool.New());
		}
		for (int i = 0; i < 100000; ++i)
		{
			TNPool.Delete(v2[i]);
		}
		v2.clear();
	}
	size_t end2 = clock();
	cout << "new cost time:" << end1 - begin1 << endl;
	cout << "object pool cost time:" << end2 - begin2 << endl;
}

//自测
void TestPool()
{
	int m = 1000;
	ObjectPool<TreeNode> obj;
	std::vector<TreeNode*> v;
	v.reserve(m);
	for (int i = 0; i < m; i++)
	{
		v.push_back(obj.New());
	}
	for (int i = 0; i < m; i++)
	{
		obj.Delete(v[i]);
	}
}